For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

Types of NoSQL Databases

Different types of NoSQL databases specialize for specific features & use-cases.

Be careful about the features you see being claimed by popular NoSQL databases.

Key-Value

Simplest type of NoSQL database.

Think of it as just a giant hashmap distributed across servers

Examples

• Redis (in-memory + optional disk persistence)
• Memcached (in-memory)
• DynamoDB (disk persistence)
• ...

How is data stored

Keys & Values (hashmap)

Both the key & the value are just plain strings (the database doesn't know & doesn't care about what is contained inside those)

Violated by most modern key-value stores.

• Redis

• Key => string
• Value => Redis supports multiple data structures (arrays, json, sets, sorted sets, bloom filter, custom data structures)

Strengths

• Extremely simple.
• Because they're typically in-memory (RAM), they're ridiculously fast!

• A single redis server can handle 100,000+ reads & writes per second!
• Compared to a SQL server which can only handle 100 writes / sec and 1000 reads / sec. A well optimized postgres server can probably handle a few thousand reads/write per second.

Queries

• get(key) ⇒ value
• set(key, value) ⇒ ack/failure
• delete(key) ⇒ ack/failure

Imagine that you’re storing a counter inside the key-value db.

How will you increment it?

In your application code

value = key_value_db.get(key)

value += 1

key_value_db.set(value)

If you increment the counter in this manner, it will lead to a race condition.

Modern databases like Redis allow you to do much more than these 3 simple operations.

        Typically increment == Get + Set.

        But redis allows you to do this in a single inc operation

Weaknesses

• No complex queries (joins / filtering)
• No search
• No indexing
• No relations

Sharding Key = Key

Automatically sharded by the hash(key)

Primary Key = Key

When to use

• Cache (global, single or distributed)
• Storing very simple data  (key-value) that needs to be queried extremely frequently (user preferences, rules, rate-limiter bucket counts, view counts)

In Redis any string has a limitation of max 500 MB.

Q: Does this mean that storing 500MB of data per entry is a good idea?

Absolutely NO!

To use key-value database, your keys <≈ 100 bytes, values <≈ 10 KB

If your keys are longer than 100 bytes, then perhaps you should look at some other database.

if your value is > 10Kb, then you probably need to dive deeper into the value – key-value is probably a poor choice.

Redis (Mandatory Reading for SDE2+)

1. Try online: https://onecompiler.com/redis
2. Quick start: https://redis.io/learn/howtos/quick-start
3. Eviction policies & Cluster mode: https://docs.google.com/document/d/1k4nzubvtX_yLctUT4VWK8ZJt4KCcOEdRJdxQgWCaiU8/

Redis (Optional Reading)

1. Tutorial: https://redis.io/university/
2. Docs: https://redis.io/docs/latest/

Document

Storing unstructured / semi-structured data.

Think of this as a collection of json/jsonb files distributed across multiple servers.

A single document will never be sharded — a single document is always stored completely within a single server (+ replicated across multiple servers)

Examples

MongoDB, ElasticSearch, Couchbase, ...

How is data stored

{

    _id:   uuidv4

    product_id: int

    name: string

    type: string            (t-shirt)

    brand: string

    color: string

    neck_type: byte

    sleeve_length: byte

    image_url: string

}

{

    _id:   uuidv4

    product_id: int

    name: string

    type: string            (laptop)

    brand: string

    color: string

    ram: {

        size: integer

        technology: string      (ddr4/ddr5/..)

        cas_latency: string

    }

    cpu: string

    image_url: [string, string, string]

}

Every document in mongodb has a unique document id.

Any document can have any set of attributes.

_id is automatically created on the client side when the document is being inserted

Strengths

• can store semi-structured / unstructured data

• schema must be enforced by the developer at the app-server level. The database will not enforce any schema.

• powerful query & search capabilities via indexes (B+trees)

• you can put an index on any top level attribute (not-nested)
• caution: indexes are maintained locally - there's no global index

• example: suppose we've amazon's product listing, & we've an index on the attribute "brand"
  then, the query mongoClient.find({brand: "dell"}) will be a fan-out read! This query will go to every shard (broadcast query) and then within each shard, the shard will use the index on "brand" to return the relevant documents
  mongoClient.find({brand: "dell", type: "laptop"}) will not be fan-out assuming that it sharded by either the brand or the type
  

• provide full-text-search

Queries

mongoClient.find( {_id: "..."} ) will fetch the document with the given document_id

mongoClient.find( {brand: "dell"} ) will fetch the documents where the value of the attribute "brand" is equal to "dell"

• if there's an index on the column, it will use this index, otherwise, it will go search through all documents.

Primary Key = _id

Sharding Key = ?

The default sharding key (if nothing else is configured) is _id

But any top-level attribute (or composite of top-level attributes) can be configured as the sharding key.

For example: for the amazon products listing we could set the sharding key as product_type (laptop/tshirt/...)

Weaknesses

• No relations & joins
• No global indexes
• (typically) no ACID transactions

• MongoDB provides ACID transactions, even across shards
• caution: ACID within the same shard is fast, but ACID across shards is extremely slow

When to use

• Unstructured / Semi-structured data
• Full-text search
• example: amazon product listing / social media posts / user notes / linkedin job posting / user reviews / …

Documents should <≈ 10MB

MongoDB has a cap of 16MB for their documents

Why such a hard limit?

Because any read/write inside a document database is at the document level.

If you modify even 1 character inside 1 attribute of a 16MB document, the database will completely rewrite this document.

You cannot modify individual attributes/values inside the document.

Similar when you read the document, you cannot read just a particular attribute of the document - the database will always read the entire document from disk.

For example,

What is the size of the boolean data type (doesn’t matter what programming language)

• 1 bit? Because a boolean is just true/false, so it should just need 1 bit
• Java / C++ / C / Rust …. a boolean is 1 byte (8 bits) where 7 bits are completely wasted!
• Python a boolean is 4 bytes

Why? Are programmers stupid? Are people who created these languages stupid?

No.

Your HDD/RAM/CPU Cache/Registers .. any memory is “byte addressable”. You can read/write individual bytes, but you can NEVER read/write individual bits.

Similarly,

• Key-Value documents are key-addressable (read/write the entire entry – unless you’re using special datatypes in Redis)
• SQL db is row addressable (read/write entire row)
• Document db is document addressable (read/write entire document)

MongoDB

1. Try online: https://mongoplayground.net/ 
2. Tutorial: https://www.mongodb.com/docs/manual/tutorial/getting-started/ 
3. Docs: https://www.mongodb.com/docs/manual/ 

Column Family / Wide Column

Wide-Column, Column Family, Columnar, … all of these are the same thing

Timeseries database are just a subset (special type) of Wide-column databases.

The data is still tabular in format (just like relational databases)

However

1. Data is stored in wide-column format (as opposed to row-wide of SQL)

1. very fast aggregate queries

2. No joins

1. data is tabular, but no relations b/w tables

Timeseries DBs are a subcategory of wide-columns DBs

Examples

Cassandra (popular), BigTable (first NoSQL db ever), ScyllaDB, HBase, ...

How is data stored

Every column family database models data in a very different manner!

The common thing is that all of them will store the data in tables, and these tables will be “partitioned” (sharded) across the servers.

Strengths

1. Highly performant for analytics (aggregate queries that span a few columns but many rows)
2. Provide easy pagination (time based)
3. Extremely fast writes!

1. Not as fast as key-value, but still, much faster than others
2. writes are fast because they use LSM trees, and because they try to make the writes sequential

Weaknesses

(same as previous - no joins, no relations, no search, no indexes…)

When to use

1. Analytics
2. High write throughput

1. sensor data (gps coordinates / IOT sensor data / ..)

3. Paginated queries / time based queries

1. fetch the location history of user in the last month

Cassandra (Optional)

1. Try online: https://jbcodeforce.github.io/db-play/

2. Introduction: https://cassandra.apache.org/_/cassandra-basics.html

3. Case Studies: https://cassandra.apache.org/_/case-studies.html

4. Architecture - Overview: https://cassandra.apache.org/doc/stable/cassandra/architecture/overview.html

5. Architecture - Guarantees: https://cassandra.apache.org/doc/stable/cassandra/architecture/guarantees.html

6. Data Modeling: Introduction | Apache Cassandra Documentation 

Large File / Object

Examples

• S3
• Google Cloud Storage
• Git Large File Storage (Git LFS)
• Hadoop Distributed File System (HDFS)

How is data stored

Flat files directly on the disk (files are chunked & distributed across servers).

The same file can be split across multiple servers.

Strengths

• These files can be extremely large (100TB file — for example, log files)
• can stream the data

Weaknesses

• No search
• No relations
• Difficult to modify files (can append, can replace, but not modify)
• reads & writes are slow

When to use

• any sort of user generated multimedia (pdf, images, videos, audios, csv, zip, ...)
• HTML/CSS/JS (if they're static, and client side)
• any large files (>10KB) that are mostly static

Others

Graph

Famous, because people have a weird attraction to graphs

But rare in practice!

• Facebook friendship / Linked follower / Twitter follower => Social connection graphs
• none of these companies stores the relationships in a graph db => all of them use SQL to store the relations

• they use a graphDB for the search queries (as a cache) in front of the SQL db

Good when your queries require "path-finding"

1. Recommender systems (Amazon / Netflix)
2. Shortest route b/w two places (Uber / Google Maps)

Vector

More popular due to AI

Provide fast K-Nearest Neighbor queries - extremely useful for searching over an embedding space

Object Oriented

Table inheritance (postgres)

.... every kid and their grandmother have their own NoSQL database type.

Multimodal

All modern database are multi-modal - they provide multiple features.

Choosing the right Database

Twitter-HashTag

Requirements

• Store the most popular & most recent tweets for each hashtag
• Paginated queries (first 20 tweets, next 20 tweets, ..)
• Very large volume of tweet writes

SQL

scale is too large!

For popular hashtags like #US-Elections-2025, #Diwali, ... a single server won't be able to store all the tweets (even for 1 hashtag)

Key-Value

Key?  "#Diwali2025 : popular"   or "#Diwali2025: recent"

Value?  all the top-100 popular/recent tweets for the hashtag, or all the tweets for the hashtag

• Value is way too large (#Diwali will have 100 millions of tweets => multiple GBs of data)
• pagination will not be possible
• inserting a tweet will require re-writing the "recent" key value which will be costly

Document DB

Same reasons as key-value

{

    __doc_id: ….

    hashtag: “Diwali 2025”

    tweets: [

          {user_id: … , … , },

          {user_id: … , … , },

          {user_id: … , … , },

    ]

}

{

    __doc_id:   == tweet_id

    hashtag: “Diwali 2025”

    content: “Celebrating crackerless pollution less diwali <3”

    author_id: Krishna

    likeCount: 1234

    viewCount: 12322

}

Column Family

HBase for example

All our requirements match exactly with the strengths of Column Family DBs.